#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include <math.h>
#include <limits.h>
#define LOCAL_TEST 0
#define M 100000

static int next_prime(int p, int pm[]){
	while(!pm[++p]);
	return p;
}
static int l_sieze(int n, int res[]){
	int pm[M], p, q, s;
	memset(pm, -1, sizeof(pm));
	for(p=2; p*p<=n; p = next_prime(p, pm)){
		for(q=p; q*p<=n; q=next_prime(q, pm)){
			for(s=p*q; s<=n; s*=p) pm[s] = 0;
		}
	}
	for(p=2, q=0, s=0; p<=n; ++p) {
		if(pm[p]){
			res[s++] = p;
			++q;
		}
	}
	return q;
}
static void factor(int n){
	static int init=0;
	int facts[M];
	int primes[M];
	int i, j, p;
	if(!init){
		l_sieze(M-10, primes);
	}
	memset(facts, 0, sizeof(facts));
	for(i=0; n>1; ++i){
		for(p=primes[i], j=0; n && n%p==0; n/=p, ++j);
		facts[i] = j;
	}
	for(j=0;j<i; ++j){
		if(facts[j]){
			printf("%d(%d)", primes[j], facts[j]);
		}
	}
	printf("\n");
}
static void solve(void){
	int x[]={72, 181944};
	int i;
	for(i=0; i<sizeof(x)/sizeof(x[0]); ++i){
		factor(x[i]);
	}
}

#if LOCAL_TEST
void run(void){
		solve();
}
#endif
